// @algorithm @lc id=744 lang=cpp 
// @title network-delay-time


#define print(...)
// @test([[2,1,1],[2,3,1],[3,4,1]],4,2)=2
// @test([[1,2,1]],2,1)=1
// @test([[1,2,1]],2,2)=-1
// @test([[1,2,1],[2,3,2],[1,3,1]],3,2)=-1
// @test([[1,2,1],[2,3,7],[1,3,4],[2,1,2]], 4, 1)=-1
// @test([[3,5,78],[2,1,1],[1,3,0],[4,3,59],[5,3,85],[5,2,22],[2,4,23],[1,4,43],[4,5,75],[5,1,15],[1,5,91],[4,1,16],[3,2,98],[3,4,22],[5,4,31],[1,2,0],[2,5,4],[4,2,51],[3,1,36],[2,3,59]], 5, 5)=31
// @test([[2,4,10],[5,2,38],[3,4,33],[4,2,76],[3,2,64],[1,5,54],[1,4,98],[2,3,61],[2,1,0],[3,5,77],[5,1,34],[3,1,79],[5,3,2],[1,2,59],[4,3,46],[5,4,44],[2,5,89],[4,5,21],[1,3,86],[4,1,95]], 5, 1)=69
// @test([[14,1,8],[11,2,25],[14,15,37],[3,7,70],[11,7,60],[13,11,87],[15,10,67],[13,10,58],[5,4,56],[9,3,26],[5,11,51],[11,4,92],[7,6,8],[7,10,95],[14,9,0],[4,13,1],[7,9,89],[3,14,24],[11,15,30],[13,2,91],[15,8,60],[1,4,96],[8,2,71],[6,8,38],[14,13,46],[2,12,48],[10,11,92],[8,12,28],[8,7,12],[9,13,82],[8,6,27],[3,2,65],[4,10,62],[11,13,55],[1,2,52],[8,3,98],[7,12,85],[6,12,97],[9,4,90],[2,4,23],[9,11,20],[1,14,61],[8,9,77],[6,5,80],[14,11,33],[9,8,54],[13,1,42],[13,8,13],[10,14,40],[9,7,18],[14,3,50],[14,6,83],[14,8,14],[2,1,86],[9,5,54],[11,5,29],[9,12,43],[9,2,74],[14,4,87],[12,7,98],[7,14,13],[4,12,33],[5,2,60],[15,11,33],[8,4,99],[9,6,98],[4,6,57],[6,11,5],[9,15,37],[1,3,30],[9,10,60],[13,12,73],[13,14,56],[1,11,13],[14,2,8],[4,15,60],[11,3,90],[2,5,86],[11,1,1],[13,4,2],[15,7,91],[15,4,51],[11,6,70],[2,7,51],[11,9,37],[4,2,92],[10,4,4],[7,2,30],[13,9,79],[8,15,41],[11,8,18],[15,2,4],[12,14,88],[12,6,9],[12,9,44],[1,6,87],[15,14,42],[4,9,41],[7,15,90],[4,1,84],[7,11,9],[3,11,75],[5,9,2],[2,11,96],[12,5,89],[6,15,25],[5,13,7],[15,5,32],[13,5,84],[7,5,9],[15,3,14],[12,13,4],[5,3,73],[6,9,85],[6,10,29],[1,8,24],[12,3,85],[4,3,60],[1,13,6],[1,5,58],[2,3,29],[14,5,67],[13,15,70],[5,14,94],[15,1,95],[3,1,17],[10,2,6],[11,10,44],[9,14,62],[4,11,32],[15,13,48],[2,10,77],[3,13,90],[5,7,68],[10,6,78],[3,6,95],[10,12,68],[13,6,73],[10,1,8],[10,7,18],[10,5,64],[5,1,55],[13,7,90],[1,9,67],[3,12,76],[14,10,22],[12,8,83],[4,7,76],[8,13,25],[5,6,57],[13,3,90],[6,2,96],[11,14,61],[12,1,94],[12,15,12],[4,8,88],[4,14,27],[7,4,25],[3,9,57],[2,15,90],[1,12,85],[12,11,44],[5,10,13],[5,12,96],[14,7,24],[14,12,98],[10,9,36],[15,6,17],[8,10,11],[2,13,5],[10,3,78],[6,13,11],[5,15,34],[12,10,12],[9,1,68],[10,13,1],[7,13,86],[1,7,62],[2,14,53],[8,14,75],[2,6,49],[10,15,83],[7,8,88],[6,1,87],[8,1,38],[8,11,73],[3,15,1],[3,8,93],[2,8,26],[4,5,26],[3,4,58],[7,1,55],[7,3,84],[5,8,97],[12,4,42],[6,3,71],[6,7,48],[15,12,3],[1,15,30],[10,8,11],[2,9,49],[6,14,9,5],[3,10,68],[6,4,14],[11,12,29],[1,10,93],[8,5,55],[12,2,86],[3,5,26],[15,9,12]],15,11)=38
// @test([[10,9,79],[15,10,58],[14,4,99],[14,12,29],[12,15,26],[1,15,78],[2,11,88],[7,3,4],[3,1,52],[11,3,91],[11,12,11],[5,10,81],[1,7,44],[12,13,52],[3,14,83],[10,4,26],[5,9,72],[5,14,32],[13,10,32],[15,6,2],[3,9,18],[1,11,45],[5,8,98],[7,13,33],[1,2,59],[4,11,79],[11,1,12],[8,5,79],[2,14,93],[3,6,53],[11,10,40],[14,2,33],[4,9,61],[3,8,10],[10,7,1],[8,3,58],[1,12,20],[5,1,51],[7,1,37],[9,7,34],[9,10,48],[8,4,90],[12,1,92],[6,4,99],[2,15,3],[2,3,80],[2,4,60],[15,14,75],[2,7,20],[15,8,20],[5,12,19],[13,3,74],[7,5,6],[9,6,73],[9,14,49],[15,1,56],[8,2,10],[7,9,9],[12,5,67],[6,3,29],[9,4,38],[6,9,42],[5,3,57],[3,2,48],[12,6,77],[10,15,15],[12,4,68],[14,1,52],[13,4,80],[4,1,84],[14,10,68],[2,12,81],[2,1,31],[6,14,52],[7,8,68],[4,12,73],[8,14,88],[13,5,92],[6,1,3],[9,11,80],[3,15,23],[15,4,84],[5,11,41],[7,11,42],[11,7,86],[9,15,63],[1,4,36],[3,13,82],[6,15,91],[13,6,64],[14,11,32],[11,5,68],[6,5,55],[4,5,35],[13,1,1],[4,10,47],[12,9,1],[7,10,44],[3,7,23],[8,12,68],[8,6,13],[2,9,19],[10,6,91],[7,12,80],[8,7,12],[4,7,4],[9,2,67],[14,9,29],[15,13,80],[6,8,62],[15,12,36],[1,3,48],[2,10,67],[9,13,55],[11,6,62],[8,11,92],[13,15,30],[4,13,97],[5,4,25],[4,2,9],[15,5,5],[15,2,45],[10,8,23],[14,5,43],[5,13,98],[14,13,73],[4,8,29],[10,5,0],[11,13,68],[9,12,91],[12,2,56],[9,1,23],[14,6,80],[9,5,10],[12,11,89],[5,15,94],[7,2,20],[3,12,89],[2,13,9],[11,2,1],[10,13,85],[6,10,76],[1,10,2],[14,15,20],[3,11,15],[11,8,62],[12,7,63],[8,15,91],[8,10,30],[12,3,80],[5,7,94],[13,2,60],[14,8,77],[10,12,67],[13,8,9],[13,11,48],[5,6,77],[10,3,51],[4,15,84],[13,12,10],[13,14,28],[4,6,46],[3,10,53],[14,7,48],[10,11,21],[15,11,99],[12,10,93],[11,14,73],[15,3,81],[2,5,22],[12,8,20],[6,13,24],[8,13,41],[8,9,98],[2,6,98],[7,15,27],[6,11,15],[7,14,72],[10,14,96],[1,8,18],[1,6,2],[3,4,78],[4,3,10],[11,4,54],[12,14,40],[3,5,63],[10,2,94],[1,9,57],[6,12,12],[9,8,37],[8,1,77],[13,7,80],[10,1,25],[9,3,37],[4,14,28],[1,13,88],[1,5,45],[7,4,65],[6,2,19],[11,15,37],[7,6,90],[2,8,1],[1,14,63],[5,2,47],[15,9,34],[11,9,41],[15,7,90],[13,9,45],[14,3,34],[6,7,44]],15,9)=49
class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        set<int> us, vs;
        const int INF = INT_MAX>>2;
        vector< vector<int> > A(n+1, vector<int>(n+1, INF));
        for(auto & uvw : times){
            A[uvw[0]][uvw[1]] = uvw[2];
            if(k!=uvw[0]) vs.insert(uvw[0]);
            if(k!=uvw[1]) vs.insert(uvw[1]);
        }
        if(vs.empty() || vs.size() < n-1) return -1;
        for(int i=0;i<n+1;i++) A[i][i] = 0;
        us.insert(k);
        print("us=", us, "\n")
        print("vs=", vs, "\n")
        while(!vs.empty()){
            int to = -1, dist = INF;
            for(auto & v : vs){
                if(A[k][v]<dist){
                    to = v;
                    dist = A[k][v];
                }
            }
            if(INF == dist) return -1;
            for(int u=1; u<n+1; u++){
                if(A[k][u] > A[k][to] + A[to][u]){
                    A[k][u] = A[k][to] + A[to][u];
                    print("<", A[k][u], "> ")
                }else{
                    print(A[k][u], " ")
                }
            }
            vs.erase(to);
            us.insert(to);
            print("\nv=", to, ", dist=", dist, ", us=", us, "\n\n")
        }
        if(!vs.empty()) return -1;
        int ans = 0;
        for(int i=1; i<n+1; i++)
            ans = max(ans, A[k][i]);
        return ans;
    }
};